package com.dmall.play.interview.chapter07;

public class Leetcode111V2 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMin = minDepth(root.left);
        int rightMin = minDepth(root.right);

        return root.left == null || root.right == null ? leftMin + rightMin + 1 : Math.min(leftMin, rightMin) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 3;
        root.right = new TreeNode();
        root.right.val = 4;
        root.right.right = new TreeNode();
        root.right.right.val = 5;
        root.right.right.right = new TreeNode();
        root.right.right.right.val = 6;

        Leetcode111V2 leetcode = new Leetcode111V2();
        int minDepth = leetcode.minDepth(root);
        System.out.println(minDepth);
    }
}
